GermanWikipedia - /page/entry.mu

Micron Document

<!DOCTYPE html>

<title>Unendlicher Graph</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Unendlicher Graph</span></h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr"><p>Als <b>unendlichen Graph</b> bezeichnet man in der <a href="Graphentheorie" title="Graphentheorie">Graphentheorie</a> einen <a href="Graph_(Graphentheorie)" title="Graph (Graphentheorie)">Graphen</a>, dessen Knoten- oder Kantenzahl unendlich ist. Spricht man hingegen von einem <i>Graphen</i> so wird oft angenommen, dass Knoten- und Kantenzahl endlich sind. Ein Graph wird als <b>wegendlich</b> bezeichnet, falls er, trotz möglicherweise unendlich vieler Knoten, keinen unendlich langen <a href="Weg_(Graphentheorie)" title="Weg (Graphentheorie)">Weg</a> besitzt.

</p><p>Aussagen über unendliche Graphen lassen sich häufig mittels eines <a href="Kompaktheitssatz_(Logik)" title="Kompaktheitssatz (Logik)">Kompaktheitsarguments</a> aus entsprechenden Aussagen über endliche Graphen ableiten. Beispielsweise ist jeder unendliche planare Graph <a href="Vier-Farben-Satz" title="Vier-Farben-Satz">vierfärbbar</a>, weil dies für jeden endlichen planaren Graphen gilt. Dies beruht auf dem <a href="Lemma_von_K%C3%B6nig" title="Lemma von König">Lemma von König</a>.

</p><p>Andere Aussagen sind nicht zwangsläufig auf unendliche Graphen übertragbar.

</p>

<div class="mw-heading mw-heading2"><h2 id="Beispiele">Beispiele</h2></div>

<p><a href="Cayley-Graph" class="mw-redirect" title="Cayley-Graph">Cayley-Graphen</a> unendlicher Gruppen <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Gamma }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Gamma }</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4cfde86a3f7ec967af9955d0988592f0693d2b19.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.453ex; height:2.176ex;" alt="{\displaystyle \Gamma }" loading="lazy"></span> sind Beispiele unendlicher Graphen mit sehr hoher Symmetrie. (Alle Elemente der Gruppe <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Gamma }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Gamma }</annotation>

</semantics>

</p><p>In vielen inner- und außermathematischen Anwendungen sind <a href="Expander-Graph" title="Expander-Graph">Expander-Graphen</a> von Bedeutung.

</p>

<div class="mw-heading mw-heading2"><h2 id="Lokal_endliche_Graphen">Lokal endliche Graphen</h2></div>

<p>Ein Graph heißt <i>lokal endlich</i>, wenn jeder Knoten nur endlich viele Nachbarn hat.

</p>

<div class="mw-heading mw-heading2"><h2 id="Feine_Graphen">Feine Graphen</h2></div>

<p>Eine in der <a href="Geometrische_Gruppentheorie" title="Geometrische Gruppentheorie">geometrischen Gruppentheorie</a> wichtige Klasse von Graphen sind <a href="Feiner_Graph" title="Feiner Graph">feine Graphen</a>, sie umfassen lokal endliche Graphen und zum Beispiel den <a href="Farey-Graph" title="Farey-Graph">Farey-Graph</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Anwendung">Anwendung</h2></div>

<p>In der <a href="Funktionalanalysis" title="Funktionalanalysis">Funktionalanalysis</a> treten unendliche Graphen als sogenannte <a href="Bratteli-Diagramm" title="Bratteli-Diagramm">Bratteli-Diagramme</a> bei der Untersuchung von <a href="AF-C*-Algebra" title="AF-C*-Algebra">AF-C*-Algebren</a> auf.

</p>

<div class="mw-heading mw-heading2"><h2 id="Sätze"><span id="S.C3.A4tze"></span>Sätze</h2></div>

<p>Zu den Sätzen über endliche Graphen, die Erweiterungen auf unendliche Graphen haben, gehören:

</p>

<ul><li>der <a href="Heiratssatz" title="Heiratssatz">Heiratssatz</a> von <a href="Philip_Hall" title="Philip Hall">Philip Hall</a>, bewiesen von <a href="Ron_Aharoni" title="Ron Aharoni">Ron Aharoni</a>, Crispin Nash-Williams und <a href="Saharon_Shelah" title="Saharon Shelah">Saharon Shelah</a>.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> Ebenso auf den unendlichen Fall übertragbar sind die Verallgemeinerung des Heiratssatzes von Richard Rado und der <a href="Satz_von_Dilworth" title="Satz von Dilworth">Satz von Dilworth</a>.</li>

<li>Der <a href="Satz_von_K%C3%B6nig_(Graphentheorie)" title="Satz von König (Graphentheorie)">Satz von König</a>, wie schon <a href="Paul_Erd%C5%91s" title="Paul Erdős">Paul Erdős</a> vermutete und wie Aharoni bewies.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup></li>

<li>der <a href="Satz_von_Menger" title="Satz von Menger">Satz von Menger</a>, bewiesen von Aharoni und Eli Berger.<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li><a href="D%C3%A9nes_K%C5%91nig" title="Dénes Kőnig">Dénes Kőnig</a>: <i>Theorie der endlichen und unendlichen Graphen. Kombinatorische Topologie der Streckenkomplexe</i>, Akademische Verlagsgesellschaft, Leipzig 1936</li>

<li><a href="Reinhard_Diestel" title="Reinhard Diestel">Reinhard Diestel</a>: <i>Infinite graphs</i>, Kapitel 8 in Reinhard Diestel: <i>Graph theory. 4th [electronic] edition 2010. Corrected reprint 2012</i>, Springer, 2012, ISBN 978-3-642-14278-9, S. 203–268 (englisch; <a rel="nofollow" class="external text" href="http://d-nb.info/1003136702/04">Inhaltsverzeichnis</a>)</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-1"><span class="mw-cite-backlink"><a href="#cite_ref-1">↑</a></span> <span class="reference-text">R. Aharoni, C. S. J. A. Nash-Williams, S. Shelah,. Marriage in infinite societies, in: Progress in Graph Theory (Waterloo, Ontario, 1982), Academic Press, Toronto, 1984, S. 71–79</span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><a href="#cite_ref-2">↑</a></span> <span class="reference-text">R. Aharoni, C. S. J. A. Nash-Williams, S. Shelah, A general criterion for the existence of transversals, Proceedings of the London Mathematical Society, Band 3, 1983, S. 43–68.</span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><a href="#cite_ref-3">↑</a></span> <span class="reference-text">R. Aharoni, C. S. J. A. Nash-Williams, S. Shelah, Another Form of a Criterion for the Existence of Transversals, Journal of the London Mathematical Society, Band 2, 1984, S. 193–203</span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><a href="#cite_ref-4">↑</a></span> <span class="reference-text">Aharoni, König's duality theorem for infinite bipartite graphs, Journal of the London Mathematical Society, Band 2, 1984, S. 1–12</span>

</li>

<li id="cite_note-5"><span class="mw-cite-backlink"><a href="#cite_ref-5">↑</a></span> <span class="reference-text">Aharoni, On a duality principle in infinite bipartite graphs, Journal of the London Mathematical Society, Band 2, 1983, S. 385–392</span>

</li>

<li id="cite_note-6"><span class="mw-cite-backlink"><a href="#cite_ref-6">↑</a></span> <span class="reference-text">R. Aharoni, E. Berger, Menger’s theorem for infinite graphs, Inventiones Mathematicae, Band 176, 2009, S. 1–62</span>

</li>

</ol></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2023-06-11" href="https://de.wikipedia.org/wiki/?title=Unendlicher_Graph&oldid=234528937">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>